package array.sliding_window;

/**
 * 将 X 减到 0 的最小操作数
 */
public class MinOperations {

    public int minOperations(int[] nums, int x) {
        int n = nums.length, sum = 0;
        for (int i = 0; i < n; i++) sum += nums[i];
        // 逆向思维：去除和为x的最小步骤， 转换为保留sum - x 的最长子序列，滑动窗口需要选找的子数组目标和
        int target = sum - x;
        // 记录窗口内所有元素和
        int windowSum = 0;
        int left = 0, right = 0;
        // 记录目标数组的最大长度
        int maxLen = Integer.MIN_VALUE;
        while (right < n) {
            windowSum += nums[right];
            right++;

            while (windowSum > target && left < right) {
                windowSum -= nums[left];
                left++;
            }

            // 寻找目标子数组,即最小操作数
            if (windowSum == target) {
                maxLen = Math.max(maxLen, right - left);
            }
        }
        return maxLen == Integer.MIN_VALUE ? -1 : n - maxLen;
    }
}
